package 中等.滑动窗口;

import java.util.TreeMap;

/**
 * 给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：
 * i，i + 1 ，...，j  表示子数组中的下标。对于所有满足 i <= i1, i2 <= j 的下标对，都有 0 <= |nums[i1] - nums[i2]| <= 2 。
 * 请你返回 不间断 子数组的总数目。
 * 子数组是一个数组中一段连续 非空 的元素序列。
 *
 * @ https://leetcode.cn/problems/continuous-subarrays/description/
 * @date 2024/10/17
 */
public class 不间断子数组_2762 {

    public static void main(String[] args) {

    }

    /**
     * 滑动窗口+平衡树
     * 滑动窗口中用平衡树维护，可以快速求出窗口中的最大值和最小值
     * 窗口 [left,right] 可以提供 right-left+1 个子数组
     */
    public long continuousSubarrays(int[] nums) {
        long ans = 0;

        TreeMap<Integer, Integer> treeMap = new TreeMap<>((a, b) -> a - b);
        int left = 0, right = 0;
        while (left < nums.length) {

            while (right < nums.length && (treeMap.isEmpty() || (
                    Math.abs(treeMap.lastKey() - nums[right]) <= 2 &&
                            Math.abs(treeMap.firstKey() - nums[right]) <= 2))) {
                treeMap.put(nums[right], treeMap.getOrDefault(nums[right], 0) + 1);
                right++;
            }
            ans += right - left;

            Integer leftCnt = treeMap.get(nums[left]);
            treeMap.put(nums[left], leftCnt - 1);
            if (leftCnt == 1) {
                treeMap.remove(nums[left]);
            }
            left++;
        }

        return ans;
    }

}
